package com.zl.heap;

/**
 * @author zengle
 * @create 2021-05-29 23:05
 */
public class QuickSort {

    public void quickSort(int[] arr, int left, int right) {
        if (left >= right || arr.length < 2) {
            return;
        }

        int pivot = partision(arr, left, right);

        if (left < right) {
            quickSort(arr, left, pivot);
            quickSort(arr, pivot + 1, right);
        }
    }

    private int partision(int[] arr, int left, int right) {
        int low = left, high = right;

        int tmp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[high] = tmp;

        return low;
    }
}
